package cn.rocky.structures.hash_table;

/**
 * 说明: 合并散列是开放寻址和单独链接的混合,碰撞但节点在哈希表中链接。
 * 此算法适合固定分配内存的哈希桶,
 * 通过存放元素时识别哈希桶上的最大空槽位来解决合并哈希中的冲突。
 *
 * 合并散列的最大目的在于将碰撞元素链接起来,避免因为需要寻找碰撞元素所发生的循环遍历。
 * 也就是说A、B元素存放时发生碰撞，那么在找到A元素的时候可以很快的索引到B元素所在的位置。
 */
public class HashMap04ByCoalescedHashing<K,V> implements Map<K,V>{

    private final Node<K, V>[] tab = new Node[8];

    @Override
    public void put(K key, V value) {
        int idx = key.hashCode() & (tab.length - 1);
        if (tab[idx] == null) {
            tab[idx] = new Node<>(key, value);
            return;
        }
        int cursor = tab.length - 1;
        while (tab[cursor] != null && tab[cursor].key != key) {
            --cursor;
        }
        tab[cursor] = new Node<>(key, value);
        // 将碰撞节点指向这个新节点
        while (tab[idx].idxOfNext != 0) {
            idx = tab[idx].idxOfNext;
        }

        tab[idx].idxOfNext = cursor;
    }

    @Override
    public V get(K key) {
        int idx = key.hashCode() & (tab.length - 1);
        while (tab[idx].key != key) {
            idx = tab[idx].idxOfNext;
        }
        return tab[idx].value;
    }

    static class Node<K, V> {
        final K key;
        V value;
        int idxOfNext;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < tab.length; i++) {
            if (tab[i] == null || tab[i].key == null) {
                continue;
            }
            stringBuilder.append("第").append(i).append("个元素,Key:").append(tab[i].key).append(",value:").append(tab[i].value).append("\n");
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        Map<String, String> map = new HashMap04ByCoalescedHashing<>();
        map.put("01", "花花");
        map.put("05", "豆豆");
        System.out.println("碰撞前 key：" + "01" + " value：" + map.get("01"));

        // 下标碰撞
        map.put("09", "蛋蛋");
        map.put("12", "苗苗");
        System.out.println("碰撞前 key：01 value：" + map.get("01"));
        System.out.println("碰撞前 key：09 value：" + map.get("09"));

        System.out.println("09".hashCode() & 7);
        System.out.println("01".hashCode() & 7);
        System.out.println(map);
    }
}
